/**
 * 
 */
package leetCode;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author zhong
 *
 */
public class ThreeSumWithMultiplicity {

	static int mod = 1000000007;
	static java.math.BigInteger modBigInteger = new BigInteger("1000000007");

	public int threeSumMulti(int[] A, int target) {
		int res = 0;
		Map<Integer, Integer> freq = getFreq(A);
		List<int[]> sumTuples = findTuples(freq, target);
		res = getCnt(sumTuples, freq);
		return res;
	}

	private int getCnt(List<int[]> sumTuples, Map<Integer, Integer> freq) {
		int res = 0;
		for (int[] is : sumTuples) {
			Map<Integer, Integer> smallMap = getFreq(is);
			long sum = 1;
			for (int i : smallMap.keySet()) {
				long pick = lucas(smallMap.get(i), freq.get(i), mod);
				sum *= pick;
				sum %= mod;
			}
			res += sum;
			res %= mod;
		}
		return res;
	}

	private static int lucas(int m, int n, int mod2) {
		if (m > n) {
			return 0;
		}
		BigInteger up = getProduct(n - m + 1, n);
		BigInteger below = getProduct(1, m);
		return up.divide(below).mod(modBigInteger).intValue();
	}

	private static BigInteger getProduct(int i, int integer) {
		BigInteger res = new BigInteger("1");
		for (int j = i; j <= integer; j++) {
			res = res.multiply(new BigInteger(String.valueOf(j)));
		}
		return res;
	}

	// public static long C(long n, long m, long p) {
	// if (m > n)
	// return 0;
	// long x = 1, y = 1;
	// while (m != 0) {
	// x = (x * n) % p;
	// y = (y * m) % p;
	// n--;
	// m--;
	// }
	// long res = x * quickpow(y, p - 2, 1) % p;
	// System.out.println("C " + "_" + n + "^" + m + "=" + res);
	// return res;
	// }
	//
	// // 组合数 公式
	// public static long lucas(long n, long m, long p) {
	// if (m == 0)
	// return 1;
	// long res = C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
	// System.out.println("lucas _" + n + "^" + m + "=" + res);
	// return res;
	// }// 幂乘函数,得到的是 (a^b)%c
	//
	// public static long quickpow(long a, long b, long mod) {
	// long ans = 1;
	// long tmpa = a;
	// while (b != 0) {
	// if ((b & 1) == 1)
	// ans = ans * a % mod;
	// tmpa = tmpa * tmpa % mod;
	// b >>= 1;
	// }
	// System.out.println("quickpow " + a + "^" + b + "=" + ans);
	// return ans;
	// }

	private List<int[]> findTuples(Map<Integer, Integer> freq, int target) {
		List<int[]> res = new ArrayList<>();
		Object[] tmpkeys = freq.keySet().toArray();
		int[] keys = transform(tmpkeys);
		Arrays.sort(keys);
		for (int i = 0; i < keys.length; i++) {
			int vali = keys[i];
			for (int j = i; j < keys.length; j++) {
				int valj = keys[j];
				int otherValue = target - vali - valj;
				if (otherValue >= valj && freq.containsKey(otherValue)) {
					res.add(new int[] { vali, valj, otherValue });
				}
			}
		}
		return res;
	}

	private int[] transform(Object[] tmpkeys) {
		int[] res = new int[tmpkeys.length];
		for (int i = 0; i < res.length; i++) {
			res[i] = (int) tmpkeys[i];
		}
		return res;
	}

	private Map<Integer, Integer> getFreq(int[] a) {
		Map<Integer, Integer> res = new HashMap<>();
		for (int i : a) {
			res.put(i, res.getOrDefault(i, 0) + 1);
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int A[] = { 1, 1, 2, 2, 2, 2 };
		int target = 5;
		System.out.println(new ThreeSumWithMultiplicity().threeSumMulti(A, target));
		// System.out.println(lucas(6, 6, mod));// A(6,6)就是求6*5*4*3*2*1,也就是求6的阶乘

	}

}
